package my.jwds.p310;

import com.alibaba.fastjson.JSONObject;

import java.util.*;

public class FindMinHeightTrees {

    public static void main(String[] args) {

        Solution1 obj = new FindMinHeightTrees.Solution1();
        int[][] edges = JSONObject.parseObject("[[1,0],[1,2],[1,3]]",int[][].class);

        long start = System.currentTimeMillis();
        System.out.println(obj.findMinHeightTrees(edges.length+1,edges));
        System.out.println("运行时间:" + (System.currentTimeMillis() - start));
    }

    /**
     * 暴力
     */
    static class Solution{
        Map<Integer,List<Integer>> map;
        public List<Integer> findMinHeightTrees(int n, int[][] edges) {
            if (n==1)return Arrays.asList(new Integer[]{0});
            map = new HashMap<>();
            for (int[] edge : edges) {
                map.putIfAbsent(edge[0],new ArrayList<>());
                map.putIfAbsent(edge[1],new ArrayList<>());
                map.get(edge[0]).add(edge[1]);
                map.get(edge[1]).add(edge[0]);
            }

            int minHeight = Integer.MAX_VALUE;
            List<Integer> roots = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                int height = getHeight(new HashSet<>(),i,minHeight);
                if (height < minHeight){
                    minHeight = height;
                    roots.clear();
                }
                if (height == minHeight){
                    roots.add(i);
                }
            }
            return roots;
        }


        int getHeight(Set<Integer> cache,Integer root,int minHeight){
            cache.add(root);
            List<Integer> list = map.get(root);
            List<Integer> nodes = new ArrayList<>();
            for (Integer integer : list) {
                if (cache.contains(integer))continue;
                cache.add(integer);
                nodes.add(integer);
            }
            int max = -1;
            for (Integer node : nodes) {
                int height = getHeight(cache,node,minHeight);
                if (height > minHeight)return minHeight+1;
                if (height > max)max = height;
            }
            return max+1;
        }
    }

    /**
     * 树形动态规划
     */
    static class Solution1{
        Map<Integer,List<Integer>> map = new HashMap<>();
        int []f1,f2,g,p;
        public List<Integer> findMinHeightTrees(int n, int[][] edges) {
            f1 = new int[n];f2 = new int[n];g = new int[n];p = new int[n];
            for (int i = 0; i < n; i++) {
                map.put(i,new ArrayList<>());
            }
            for (int[] edge : edges) {
                map.get(edge[0]).add(edge[1]);
                map.get(edge[1]).add(edge[0]);
            }

            dfs(0,-1);
            dfs1(0,-1);
            int minHeight = Integer.MAX_VALUE;
            List<Integer> roots = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                int height = Integer.max(f1[i],g[i]);
                if (height < minHeight){
                    minHeight = height;
                    roots.clear();
                }
                if (height == minHeight){
                    roots.add(i);
                }
            }
            return roots;

        }


        int dfs(int node,int prev){
            List<Integer> children = map.get(node);

            for (Integer child : children) {
                if (child == prev){
                    continue;
                }
                int height = dfs(child,node) + 1;
                if (height > f1[node]){
                    f2[node] = f1[node];
                    f1[node] = height;
                    p[node] = child;
                }else if (height > f2[node]) {
                    f2[node] = height;
                }
            }
            return f1[node];
        }

        void dfs1(int node,int prev){
            List<Integer> children = map.get(node);

            for (Integer child : children) {
                if (child == prev){continue;}

                if (child == p[node]){
                    g[child] = f2[node]+1;
                }else{
                    g[child] = f1[node]+1;
                }
                g[child] = Integer.max(g[child],g[node]+1);
                dfs1(child,node);
            }

        }

    }




}